public class Rob {
    // 打家劫舍I
    // https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79?tpId=295&tqId=2285793&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
    public int rob (int[] nums) {
        // write code here
        // d[i][0]表示不偷第i家的时候的最高金额，dp[i][1]表示偷第i家时的最高金额
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1], dp[i-2][1])
        // dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + nums[i]
        int[][] dp = new int[nums.length+2][2];
        for (int i = 2; i < nums.length + 2; i++) {
            dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-2][1]);
            dp[i][1] = Math.max(dp[i-1][0], dp[i-2][0]) + nums[i-2];
        }
        return Math.max(dp[nums.length+1][0], dp[nums.length+1][1]);
    }
}
